home *** CD-ROM | disk | FTP | other *** search
/ MPEG Toolkit / MPEG Toolkit.iso / dos / ampeg43 / source / decodsrc / huffman.c < prev    next >
Encoding:
C/C++ Source or Header  |  1997-01-01  |  10.9 KB  |  374 lines
  1. /**********************************************************************
  2. Copyright (c) 1991 MPEG/audio software simulation group, All Rights Reserved
  3. huffman.c
  4. **********************************************************************/
  5. /**********************************************************************
  6.  * MPEG/audio coding/decoding software, work in progress              *
  7.  *   NOT for public distribution until verified and approved by the   *
  8.  *   MPEG/audio committee.  For further information, please contact   *
  9.  *   Davis Pan, 708-538-5671, e-mail: pan@ukraine.corp.mot.com        *
  10.  *                                                                    *
  11.  * VERSION 4.3                                                        *
  12.  *   changes made since last update:                                  *
  13.  *   date   programmers                comment                        *
  14.  *27.2.92   F.O.Witte                  (ITT Intermetall)              *
  15.  *                       email: otto.witte@itt-sc.de    *
  16.  *                       tel:   ++49 (761)517-125          *
  17.  *                       fax:   ++49 (761)517-880          *
  18.  *12.6.92   J. Pineda                  Added sign bit to decoder.     *
  19.  * 08/24/93 M. Iwadare                 Changed for 1 pass decoding.   *
  20.  *--------------------------------------------------------------------*
  21.  *  7/14/94 Juergen Koller      Bug fixes in Layer III code           *
  22.  *********************************************************************/    
  23.  
  24. #include "common.h"
  25. #include "huffman.h"
  26.      
  27. HUFFBITS dmask = 1 << (sizeof(HUFFBITS)*8-1);
  28. unsigned int hs = sizeof(HUFFBITS)*8;
  29.  
  30. struct huffcodetab ht[HTN];    /* array of all huffcodtable headers    */
  31.                 /* 0..31 Huffman code table 0..31    */
  32.                 /* 32,33 count1-tables            */
  33.  
  34. /* read the huffman encode table */
  35. int read_huffcodetab(fi) 
  36. FILE *fi;
  37. {
  38.  
  39.   char line[100],command[40],huffdata[40];
  40.   unsigned int t,i,j,k,nn,x,y,n=0;
  41.   unsigned int xl, yl, len;
  42.   HUFFBITS h;
  43.   int    hsize;
  44.   
  45.   hsize = sizeof(HUFFBITS)*8; 
  46.   do {
  47.       fgets(line,99,fi);
  48.   } while ((line[0] == '#') || (line[0] < ' ') );
  49.   
  50.   do {    
  51.     while ((line[0]=='#') || (line[0] < ' ')) {
  52.       fgets(line,99,fi);
  53.     } 
  54.  
  55.     sscanf(line,"%s %s %u %u %u",command,ht[n].tablename,
  56.                      &xl,&yl,&ht[n].linbits);
  57.     if (strcmp(command,".end")==0)
  58.       return n;
  59.     else if (strcmp(command,".table")!=0) {
  60.       fprintf(stderr,"huffman table %u data corrupted\n",n);
  61.       return -1;
  62.     }
  63.     ht[n].linmax = (1<<ht[n].linbits)-1;
  64.    
  65.     sscanf(ht[n].tablename,"%u",&nn);
  66.     if (nn != n) {
  67.       fprintf(stderr,"wrong table number %u\n",n);
  68.       return(-2);
  69.     } 
  70.  
  71.     ht[n].xlen = xl;
  72.     ht[n].ylen = yl;
  73.  
  74.     do {
  75.       fgets(line,99,fi);
  76.     } while ((line[0] == '#') || (line[0] < ' '));
  77.  
  78.     sscanf(line,"%s %u",command,&t);
  79.     if (strcmp(command,".reference")==0) {
  80.       ht[n].ref   = t;
  81.       ht[n].table = ht[t].table;
  82.       ht[n].hlen  = ht[t].hlen;
  83.       if ( (xl != ht[t].xlen) ||
  84.            (yl != ht[t].ylen)  ) {
  85.         fprintf(stderr,"wrong table %u reference\n",n);
  86.         return (-3);
  87.       };
  88.       do {
  89.         fgets(line,99,fi);
  90.       } while ((line[0] == '#') || (line[0] < ' ') );
  91.     } 
  92.     else {
  93.       ht[n].ref  = -1;
  94.       ht[n].table=(HUFFBITS *) calloc(xl*yl,sizeof(HUFFBITS));
  95.       if (ht[n].table == NULL) {
  96.          fprintf(stderr,"unsufficient heap error\n");
  97.          return (-4);
  98.       }
  99.       ht[n].hlen=(unsigned char *) calloc(xl*yl,sizeof(unsigned char));
  100.       if (ht[n].hlen == NULL) {
  101.          fprintf(stderr,"unsufficient heap error\n");
  102.          return (-4);
  103.       }
  104.       for (i=0; i<xl; i++) {
  105.         for (j=0;j<yl; j++) {
  106.       if (xl>1) 
  107.             sscanf(line,"%u %u %u %s",&x, &y, &len,huffdata);
  108.       else 
  109.             sscanf(line,"%u %u %s",&x,&len,huffdata);
  110.           h=0;k=0;
  111.       while (huffdata[k]) {
  112.             h <<= 1;
  113.             if (huffdata[k] == '1')
  114.               h++;
  115.             else if (huffdata[k] != '0'){
  116.               fprintf(stderr,"huffman-table %u bit error\n",n);
  117.               return (-5);
  118.             };
  119.             k++;
  120.           };
  121.           if (k != len) {
  122.            fprintf(stderr,
  123.               "warning: wrong codelen in table %u, pos [%2u][%2u]\n",
  124.            n,i,j);
  125.           };
  126.           ht[n].table[i*xl+j] = h;
  127.           ht[n].hlen[i*xl+j] = (unsigned char) len;
  128.       do {
  129.             fgets(line,99,fi);
  130.           } while ((line[0] == '#') || (line[0] < ' '));
  131.         }
  132.       }
  133.     }
  134.     n++;
  135.   } while (1);
  136. }
  137.  
  138. /* read the huffman decoder table */
  139. int read_decoder_table(fi) 
  140. FILE *fi;
  141. {
  142.   int n,i,nn,t;
  143.   unsigned int v0,v1;
  144.   char command[100],line[100];
  145.   for (n=0;n<HTN;n++) {
  146.     /* .table number treelen xlen ylen linbits */ 
  147.     do {
  148.       fgets(line,99,fi);
  149.     } while ((line[0] == '#') || (line[0] < ' '));
  150.      
  151.     sscanf(line,"%s %s %u %u %u %u",command,ht[n].tablename,
  152.            &ht[n].treelen, &ht[n].xlen, &ht[n].ylen, &ht[n].linbits);
  153.     if (strcmp(command,".end")==0)
  154.       return n;
  155.     else if (strcmp(command,".table")!=0) {
  156.       fprintf(stderr,"huffman table %u data corrupted\n",n);
  157.       return -1;
  158.     }
  159.     ht[n].linmax = (1<<ht[n].linbits)-1;
  160.    
  161.     sscanf(ht[n].tablename,"%u",&nn);
  162.     if (nn != n) {
  163.       fprintf(stderr,"wrong table number %u\n",n);
  164.       return(-2);
  165.     } 
  166.     do {
  167.       fgets(line,99,fi);
  168.     } while ((line[0] == '#') || (line[0] < ' '));
  169.  
  170.     sscanf(line,"%s %u",command,&t);
  171.     if (strcmp(command,".reference")==0) {
  172.       ht[n].ref   = t;
  173.       ht[n].val   = ht[t].val;
  174.       ht[n].treelen  = ht[t].treelen;
  175.       if ( (ht[n].xlen != ht[t].xlen) ||
  176.            (ht[n].ylen != ht[t].ylen)  ) {
  177.         fprintf(stderr,"wrong table %u reference\n",n);
  178.         return (-3);
  179.       };
  180.       while ((line[0] == '#') || (line[0] < ' ') ) {
  181.         fgets(line,99,fi);
  182.       }
  183.     }    
  184.     else if (strcmp(command,".treedata")==0) {
  185.       ht[n].ref  = -1;
  186.       ht[n].val = (unsigned char (*)[2]) 
  187.         calloc(2*(ht[n].treelen),sizeof(unsigned char));
  188.       if (ht[n].val == NULL) {
  189.         fprintf(stderr, "heaperror at table %d\n",n);
  190.         exit (-10);
  191.       }
  192.       for (i=0;i<ht[n].treelen; i++) {
  193.         fscanf(fi,"%x %x",&v0, &v1);
  194.         ht[n].val[i][0]=(unsigned char)v0;
  195.         ht[n].val[i][1]=(unsigned char)v1;
  196.       }
  197.       fgets(line,99,fi); /* read the rest of the line */
  198.     }
  199.     else {
  200.       fprintf(stderr,"huffman decodertable error at table %d\n",n);
  201.     }
  202.   }
  203.   return n;
  204. }
  205.  
  206.  
  207. /* do the huffman coding,  */
  208. /* note! for counta,countb - the 4 bit value is passed in y, set x to 0 */
  209. /* return value: 0-no error, 1 decode error                */
  210. void huffman_coder( x, y, h, bs)
  211. unsigned int x;     /* x-value */
  212. unsigned int y;     /* y-value */
  213. struct huffcodetab *h;     /* pointer to huffman code record     */
  214. Bit_stream_struc *bs;      /* pointer to open write bitstream     */
  215. {
  216.   HUFFBITS huffbits; /* data left aligned */
  217.   HUFFBITS linbitsX; 
  218.   HUFFBITS linbitsY;
  219.   unsigned int len;
  220.   unsigned int xl1 = h->xlen-1;
  221.   unsigned int yl1 = h->ylen-1;
  222.   linbitsX = 0;
  223.   linbitsY = 0;
  224.   if (h->table == NULL) return;
  225.   if (((x < xl1) || (xl1==0)) && (y < yl1)) {
  226.     huffbits = h->table[x*(h->xlen)+y];
  227.     len = h->hlen[x*(h->xlen)+y];
  228.     putbits(bs,huffbits,len);
  229.     return;
  230.   }  
  231.   else if (x >= xl1) {
  232.     linbitsX = x-xl1;
  233.     if (linbitsX > h->linmax) {
  234.       fprintf(stderr,"warning: Huffman X table overflow\n");
  235.       linbitsX= h->linmax;
  236.     };
  237.     if (y >= yl1) {
  238.       huffbits = h->table[(h->ylen)*(h->xlen)-1];
  239.       len = h->hlen[(h->ylen)*(h->xlen)-1];
  240.       putbits(bs,huffbits,len);
  241.       linbitsY = y-yl1;
  242.       if (linbitsY > h->linmax) {
  243.         fprintf(stderr,"warning: Huffman Y table overflow\n");
  244.         linbitsY = h->linmax;
  245.       };
  246.       if (h->linbits) {
  247.         putbits(bs,linbitsX,h->linbits);
  248.         putbits(bs,linbitsY,h->linbits);
  249.       }
  250.     } 
  251.     else { /* x>= h->xlen, y<h->ylen */
  252.       huffbits = h->table[(h->ylen)*xl1+y];
  253.       len = h->hlen[(h->ylen)*xl1+y];
  254.       putbits(bs,huffbits,len);
  255.       if (h->linbits) {
  256.         putbits(bs,linbitsX,h->linbits);
  257.       }
  258.     }
  259.   }
  260.   else  { /* ((x < h->xlen) && (y>=h->ylen)) */
  261.     huffbits = h->table[(h->ylen)*x+yl1];
  262.     len = h->hlen[(h->ylen)*x+yl1];
  263.     putbits(bs,huffbits,len);
  264.     linbitsY = y-yl1;
  265.     if (linbitsY > h->linmax) {
  266.       fprintf(stderr,"warning: Huffman Y table overflow\n");
  267.       linbitsY = h->linmax;
  268.     };
  269.     if (h->linbits) {
  270.        putbits(bs,linbitsY,h->linbits);
  271.     }
  272.   }
  273. }
  274.  
  275. /* do the huffman-decoding                         */
  276. /* note! for counta,countb -the 4 bit value is returned in y, discard x */
  277. int huffman_decoder(h, x, y, v, w)
  278. struct huffcodetab *h;    /* pointer to huffman code record    */
  279. /* unsigned */ int *x;     /* returns decoded x value         */
  280. /* unsigned */ int *y;    /* returns decoded y value        */
  281. int *v;
  282. int *w;
  283. {  
  284.   HUFFBITS level;
  285.   int point = 0;
  286.   int error = 1;
  287.   level     = dmask;
  288.   if (h->val == NULL) return 2;
  289.  
  290.   /* table 0 needs no bits */
  291.   if ( h->treelen == 0)
  292.   {  *x = *y = 0;
  293.      return 0;
  294.   }
  295.  
  296.  
  297.   /* Lookup in Huffman table. */
  298.  
  299.   do {
  300.     if (h->val[point][0]==0) {   /*end of tree*/
  301.       *x = h->val[point][1] >> 4;
  302.       *y = h->val[point][1] & 0xf;
  303.  
  304.       error = 0;
  305.       break;
  306.     } 
  307.     if (hget1bit()) {
  308.       while (h->val[point][1] >= MXOFF) point += h->val[point][1]; 
  309.       point += h->val[point][1];
  310.     }
  311.     else {
  312.       while (h->val[point][0] >= MXOFF) point += h->val[point][0]; 
  313.       point += h->val[point][0];
  314.     }
  315.     level >>= 1;
  316.   } while (level  || (point < ht->treelen) );
  317.   
  318.   /* Check for error. */
  319.   
  320.   if (error) { /* set x and y to a medium value as a simple concealment */
  321.     printf("Illegal Huffman code in data.\n");
  322.     *x = (h->xlen-1 << 1);
  323.     *y = (h->ylen-1 << 1);
  324.   }
  325.  
  326.   /* Process sign encodings for quadruples tables. */
  327.  
  328.   if (h->tablename[0] == '3'
  329.       && (h->tablename[1] == '2' || h->tablename[1] == '3')) {
  330.      *v = (*y>>3) & 1;
  331.      *w = (*y>>2) & 1;
  332.      *x = (*y>>1) & 1;
  333.      *y = *y & 1;
  334.  
  335.      /* v, w, x and y are reversed in the bitstream. 
  336.         switch them around to make test bistream work. */
  337.      
  338. /*   {int i=*v; *v=*y; *y=i; i=*w; *w=*x; *x=i;}  MI */
  339.  
  340.      if (*v)
  341.         if (hget1bit() == 1) *v = -*v;
  342.      if (*w)
  343.         if (hget1bit() == 1) *w = -*w;
  344.      if (*x)
  345.         if (hget1bit() == 1) *x = -*x;
  346.      if (*y)
  347.         if (hget1bit() == 1) *y = -*y;
  348.      }
  349.      
  350.   /* Process sign and escape encodings for dual tables. */
  351.   
  352.   else {
  353.   
  354.       /* x and y are reversed in the test bitstream.
  355.          Reverse x and y here to make test bitstream work. */
  356.      
  357. /*    removed 11/11/92 -ag  
  358.         {int i=*x; *x=*y; *y=i;} 
  359. */      
  360.      if (h->linbits)
  361.        if ((h->xlen-1) == *x) 
  362.          *x += hgetbits(h->linbits);
  363.      if (*x)
  364.         if (hget1bit() == 1) *x = -*x;
  365.      if (h->linbits)      
  366.        if ((h->ylen-1) == *y)
  367.          *y += hgetbits(h->linbits);
  368.      if (*y)
  369.         if (hget1bit() == 1) *y = -*y;
  370.      }
  371.       
  372.   return error;  
  373. }
  374.